'''
Created on Oct 3, 2012

@author: Jason Huang
'''
import gmpy2
from gmpy2 import *

p=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g=11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
h=3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333


def solve():
    B = 2**20
    (_, g_inv, _) = gcdext(mpz(g), mpz(p))
    while g_inv < 0:
        g_inv += p
    while g_inv >= p:
        g_inv -= p

    my_dict = {}
    cur = mpz(h)

    for x in range(0, B):
        my_dict[cur] = x
        cur = t_mod(mul(cur, g_inv), mpz(p))

    print("map built")
    gg = mpz(1)
    for x in range(B):
        gg = t_mod(mul(gg, mpz(g)), mpz(p))

    cur = mpz(1)
    for x in range(B):
        print("x2 = ", x)
        if cur in my_dict:
            print("found!!!")
            print("x0 = ", x)
            print("x1 = ", my_dict[cur])
            print("ans = ", x * B + my_dict[cur])
            break
        cur = t_mod(mul(cur, gg), mpz(p))


if __name__ == '__main__':
    solve()